#include <iostream>
#include <vector>

template <class T>
class emoryPool
{
public:
    T *New()
    {
        T *obj = nullptr;
        if (_freelist)
        {
            obj = (T *)_freelist;
            void *next = *(void **)_freelist;
            _freelist = next;
        }
        else
        {
            if (_remainByte < sizeof(T))
            {
                _memory = (char *)malloc(1024 * 128);
                if (_memory == nullptr)
                {
                    std::cout << "MemoryPool New(): malloc fail" << std::endl;
                    exit(-1);
                }
            }
            obj = (T *)_memory;
            size_t objSize = sizeof(T) < sizeof(void *) ? sizeof(void*) : sizeof(T);
            _memory += objSize;
            _remainByte -= sizeof(T);
        }
        new(obj) T;

        return obj;
    }

    void Delete(T* obj)
    {
        obj->~T();
        *(void**)obj = _freelist;
        _freelist = obj;
    }
    
private:
    char *_memory = nullptr;
    size_t _remainByte = 0;
    void *_freelist = nullptr;
};

// 定长内存池类
template <class T>
class FLMemoryPool
{
public:
    T *New()
    {

        T *obj = nullptr;
        // 在还回来的内存快中重新分发内存
        if (_freeList)
        {
            // void*不可以解引用，所以为了找到下一个节点，所以把他变成二级指针进行解引用即可
            void *next = *(void **)_freeList;
            obj = (T *)_freeList;
            _freeList = next;
        }
        // 在大的内存块中进行分发内存
        else
        {
            // 当剩下的内存块不够时，在进行申请新空间
            if (_remainBytes < sizeof(T))
            {
                size_t size = 1024 * 128;
                _memory = (char *)malloc(size);
                if (_memory == nullptr)
                {
                    cout << "malloc fail" << endl;
                }
            }

            obj = (T *)_memory;
            // 保证freeList在连接时，确保能够有存放一个指针大小的空间
            size_t objSize = sizeof(T) < sizeof(void *) ? sizeof(void *) : sizeof(T);
            _memory += objSize;
            _remainBytes -= sizeof(T);
        }

        // 定位new 显示调用T的构造函数初始化
        new (obj) T;

        return obj;
    }

    void Delete(T *obj)
    {
        // 显示调用析构函数清理对象
        obj->~T();
        // 头插
        *(void **)obj = _freeList; 
        //首先是要让obj指向空间的前x个字节的值存放下一个节点的地址。
        //所以如果是32位则是*(int*)obj = _freeList; 64位则需要*(uint64_t*)obj = _freeList;
        //而上面的写法无论是32位还是64位都可以解决
        // void* 指向一个地址，但没有类型，解引用后，不知道大小(也无法解引用)
        // void**指向void*指针，指针类型的大小时明确的，所以解引用后可以赋值
        // 而具体是4/8字节，*(void**)就可以知道，因为void*是指针类型，有明确的大小
        // 和*(int*)一样，对于int类型解引用是访问int字节空间，*(void**)则是访问一个指针类型的空间大小
        // 这里只需要是个二级指针即可，因为int*和void*的大小是一样的

        _freeList = obj;
    }

private:
    char *_memory = nullptr;   // 指向大块内存的指针
    size_t _remainBytes = 0;   // 大块内存中剩余的字节数
    void *_freeList = nullptr; // 还回的内存链表头指针
};

struct TreeNode
{
    int _val;
    TreeNode *_left;
    TreeNode *_right;
    TreeNode()
        : _val(0), _left(nullptr), _right(nullptr)
    {
    }
};
void TestObjectPool()
{
    // 申请释放的轮次
    const size_t Rounds = 3;
    // 每轮申请释放多少次
    const size_t N = 100000;
    size_t begin1 = clock();
    std::vector<TreeNode *> v1;
    v1.reserve(N);
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            v1.push_back(new TreeNode);
        }
        for (int i = 0; i < N; ++i)
        {
            delete v1[i];
        }
        v1.clear();
    }
    size_t end1 = clock();

    std::cout << "aaaaaaaaaaaaaa" << std::endl;
    FLMemoryPool<TreeNode> TNPool;
    size_t begin2 = clock();
    std::vector<TreeNode *> v2;
    v2.reserve(N);
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            v2.push_back(TNPool.New());
        }
        for (int i = 0; i < 100000; ++i)
        {
            TNPool.Delete(v2[i]);
        }
        v2.clear();
    }
    size_t end2 = clock();
    std::cout << "new cost time:" << end1 - begin1 << std::endl;
    std::cout << "object pool cost time:" << end2 - begin2 << std::endl;
}

int main()
{
    TestObjectPool();
    return 0;
}